Thực đơn
RSA (mã hóa) Hoạt độngThuật toán RSA có hai khóa: khóa công khai (hay khóa công cộng) và khóa bí mật (hay khóa cá nhân). Mỗi khóa là những số cố định sử dụng trong quá trình mã hóa và giải mã. Khóa công khai được công bố rộng rãi cho mọi người và được dùng để mã hóa. Những thông tin được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng khóa bí mật tương ứng. Nói cách khác, mọi người đều có thể mã hóa nhưng chỉ có người biết khóa cá nhân (bí mật) mới có thể giải mã được.
Ta có thể mô phỏng trực quan một hệ mật mã khoá công khai như sau: Bình muốn gửi cho An một thông tin mật mà Bình muốn duy nhất An có thể đọc được. Để làm được điều này, An gửi cho Bình một chiếc hộp có khóa đã mở sẵn và giữ lại chìa khóa. Bình nhận chiếc hộp, cho vào đó một tờ giấy viết thư bình thường và khóa lại (như loại khoá thông thường chỉ cần sập chốt lại, sau khi sập chốt khóa ngay cả Bình cũng không thể mở lại được-không đọc lại hay sửa thông tin trong thư được nữa). Sau đó Bình gửi chiếc hộp lại cho An. An mở hộp với chìa khóa của mình và đọc thông tin trong thư. Trong ví dụ này, chiếc hộp với khóa mở đóng vai trò khóa công khai, chiếc chìa khóa chính là khóa bí mật.
Giả sử An và Bình cần trao đổi thông tin bí mật thông qua một kênh không an toàn (ví dụ như Internet). Với thuật toán RSA, An đầu tiên cần tạo ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bước sau:
Một số lưu ý:
Khóa công khai bao gồm:
Khóa bí mật bao gồm:
Một dạng khác của khóa bí mật bao gồm:
Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dư Trung Quốc (tiếng Anh: Chinese Remainder Theorem - CRT). Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí mật.
An gửi khóa công khai cho Bình, và giữ bí mật khóa cá nhân của mình. Ở đây, p và q giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e. Nếu không sử dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa ngay sau khi thực hiện xong quá trình tạo khóa.
Giả sử Bình muốn gửi đoạn thông tin M cho An. Đầu tiên Bình chuyển M thành một số m < n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước. Quá trình này được mô tả ở phần #Chuyển đổi văn bản rõ.
Lúc này Bình có m và biết n cũng như e do An gửi. Bình sẽ tính c là bản mã hóa của m theo công thức:
c = m e mod n {\displaystyle c=m^{e}\mod {n}}Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng (thuật toán bình phương và nhân) Cuối cùng Bình gửi c cho An.
An nhận c từ Bình và biết khóa bí mật d. An có thể tìm được m từ c theo công thức sau:
m = c d mod n {\displaystyle m=c^{d}\mod {n}}Biết m, An tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình giải mã hoạt động vì ta có
c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{\pmod {n}}} .Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo Định lý Fermat nhỏ) nên:
m e d ≡ m ( mod p ) {\displaystyle m^{ed}\equiv m{\pmod {p}}}và
m e d ≡ m ( mod q ) {\displaystyle m^{ed}\equiv m{\pmod {q}}}Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý số dư Trung Quốc, ta có:
m e d ≡ m ( mod p q ) {\displaystyle m^{ed}\equiv m{\pmod {pq}}} .hay:
c d ≡ m ( mod n ) {\displaystyle c^{d}\equiv m{\pmod {n}}} .Sau đây là một ví dụ với những số cụ thể. Ở đây chúng ta sử dụng những số nhỏ để tiện tính toán còn trong thực tế phải dùng các số có giá trị đủ lớn.
Lấy:
p = 61 | — số nguyên tố thứ nhất (giữ bí mật hoặc hủy sau khi tạo khóa) |
q = 53 | — số nguyên tố thứ hai (giữ bí mật hoặc hủy sau khi tạo khóa) |
n = pq = 3233 | — môđun (công bố công khai) |
e = 17 | — số mũ công khai |
d = 2753 | — số mũ bí mật |
Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là:
encrypt(m) = me mod n = m17 mod 3233với m là văn bản rõ. Hàm giải mã là:
decrypt(c) = cd mod n = c2753 mod 3233với c là văn bản mã.
Để mã hóa văn bản có giá trị 123, ta thực hiện phép tính:
encrypt(123) = 12317 mod 3233 = 855Để giải mã văn bản có giá trị 855, ta thực hiện phép tính:
decrypt(855) = 8552753 mod 3233 = 123Cả hai phép tính trên đều có thể được thực hiện hiệu quả nhờ thuật toán bình phương và nhân.
Trước khi thực hiện mã hóa, ta phải thực hiện việc chuyển đổi văn bản rõ (chuyển đổi từ M sang m) sao cho không có giá trị nào của M tạo ra văn bản mã không an toàn. Nếu không có quá trình này, RSA sẽ gặp phải một số vấn đề sau:
Trên thực tế, ta thường gặp 2 vấn đề đầu khi gửi các bản tin ASCII ngắn với m là nhóm vài ký tự ASCII. Một đoạn tin chỉ có 1 ký tự NUL
sẽ được gán giá trị m = 0 và cho ra bản mã là 0 bất kể giá trị của e và N. Tương tự, một ký tự ASCII khác, SOH
, có giá trị 1 sẽ luôn cho ra bản mã là 1. Với các hệ thống dùng giá trị e nhỏ thì tất cả ký tự ASCII đều cho kết quả mã hóa không an toàn vì giá trị lớn nhất của m chỉ là 255 và 2553 nhỏ hơn giá trị n chấp nhận được. Những bản mã này sẽ dễ dàng bị phá mã.
Để tránh gặp phải những vấn đề trên, RSA trên thực tế thường bao gồm một hình thức chuyển đổi ngẫu nhiên hóa m trước khi mã hóa. Quá trình chuyển đổi này phải đảm bảo rằng m không rơi vào các giá trị không an toàn. Sau khi chuyển đổi, mỗi bản rõ khi mã hóa sẽ cho ra một trong số khả năng trong tập hợp bản mã. Điều này làm giảm tính khả thi của phương pháp tấn công lựa chọn bản rõ (một bản rõ sẽ có thể tương ứng với nhiều bản mã tuỳ thuộc vào cách chuyển đổi).
Một số tiêu chuẩn, chẳng hạn như PKCS, đã được thiết kế để chuyển đổi bản rõ trước khi mã hóa bằng RSA. Các phương pháp chuyển đổi này bổ sung thêm bít vào M. Các phương pháp chuyển đổi cần được thiết kế cẩn thận để tránh những dạng tấn công phức tạp tận dụng khả năng biết trước được cấu trúc của bản rõ. Phiên bản ban đầu của PKCS dùng một phương pháp đặc ứng (ad-hoc) mà về sau được biết là không an toàn trước tấn công lựa chọn bản rõ thích ứng (adaptive chosen ciphertext attack). Các phương pháp chuyển đổi hiện đại sử dụng các kỹ thuật như chuyển đổi mã hóa bất đối xứng tối ưu (Optimal Asymmetric Encryption Padding - OAEP) để chống lại tấn công dạng này. Tiêu chuẩn PKCS còn được bổ sung các tính năng khác để đảm bảo an toàn cho chữ ký RSA (Probabilistic Signature Scheme for RSA - RSA-PSS).
Thuật toán RSA còn được dùng để tạo chữ ký số cho văn bản. Giả sử An muốn gửi cho Bình một văn bản có chữ ký của mình. Để làm việc này, An tạo ra một giá trị băm (hash value) của văn bản cần ký và tính giá trị mũ d mod n của nó (giống như khi An thực hiện giải mã). Giá trị cuối cùng chính là chữ ký điện tử của văn bản đang xét. Khi Bình nhận được văn bản cùng với chữ ký điện tử, anh ta tính giá trị mũ e mod n của chữ ký đồng thời với việc tính giá trị băm của văn bản. Nếu 2 giá trị này như nhau thì Bình biết rằng người tạo ra chữ ký biết khóa bí mật của An và văn bản đã không bị thay đổi sau khi ký.
Cần chú ý rằng các phương pháp chuyển đổi bản rõ (như RSA-PSS) giữ vai trò quan trọng đối với quá trình mã hóa cũng như chữ ký điện tử và không được dùng khóa chung cho đồng thời cho cả hai mục đích trên.
Thực đơn
RSA (mã hóa) Hoạt độngLiên quan
RSA (định hướng) RSA (mã hóa) Real Madrid CF RSS (định dạng tập tin) Rafael Nadal RS-28 Sarmat Ready Player One: Đấu trường ảo Rau RSVP (giao thức) Rap Việt (mùa 3)Tài liệu tham khảo
WikiPedia: RSA (mã hóa) http://www.rsasecurity.com/rsalabs/node.asp?id=212... http://theory.lcs.mit.edu/~rivest/rsapaper.pdf